import java.util.Arrays;

/*public class ttt {
}*/
/*
import java.math.BigInteger;

public class KaratsubaMultiplication {
    // Karatsuba 分治递归函数
    private static BigInteger karatsuba(BigInteger x, BigInteger y) {
        int n = Math.max(x.bitLength(), y.bitLength());
        // 终止条件：当位数小于等于 2 时，直接使用 BigInteger 的 multiply 方法计算
        if (n <= 2) {
            return x.multiply(y);
        }

        // 计算拆分的位置，将 n 向上取半
        n = (n + 1) / 2;
        BigInteger tenPowerN = BigInteger.TEN.pow(n);
        BigInteger tenPower2N = BigInteger.TEN.pow(2 * n);

        // 拆分 x 为 x1（高位部分）和 x0（低位部分）
        BigInteger x1 = x.divide(tenPowerN);
        BigInteger x0 = x.mod(tenPowerN);
        // 拆分 y 为 y1（高位部分）和 y0（低位部分）
        BigInteger y1 = y.divide(tenPowerN);
        BigInteger y0 = y.mod(tenPowerN);

        // 递归计算三个小乘积
        BigInteger p1 = karatsuba(x1, y1);
        BigInteger p0 = karatsuba(x0, y0);
        BigInteger p2 = karatsuba(x1.add(x0), y1.add(y0));

        // 合并结果：p1*10^(2n) + (p2 - p1 - p0)*10^n + p0
        return p1.multiply(tenPower2N)
                .add(p2.subtract(p1).subtract(p0).multiply(tenPowerN))
                .add(p0);
    }

    // 入口方法，接收字符串形式的大整数
    public static BigInteger multiply(String num1, String num2) {
        BigInteger x = new BigInteger(num1);
        BigInteger y = new BigInteger(num2);
        return karatsuba(x, y);
    }

    // 测试方法
    public static void main(String[] args) {
        String a = "12345678901234567890";
        String b = "98765432109876543210";
        System.out.println("Karatsuba 算法计算结果：" + multiply(a, b));
        // 用 BigInteger 自带的 multiply 方法验证结果
        BigInteger bigA = new BigInteger(a);
        BigInteger bigB = new BigInteger(b);
        System.out.println("BigInteger 自带方法计算结果：" + bigA.multiply(bigB));
    }
}
*/
public class StrassenMatrixMultiplication {
    // 矩阵加法
    private static int[][] add(int[][] a, int[][] b) {
        int n = a.length;
        int[][] res = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                res[i][j] = a[i][j] + b[i][j];
            }
        }
        return res;
    }

    // 矩阵减法
    private static int[][] subtract(int[][] a, int[][] b) {
        int n = a.length;
        int[][] res = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                res[i][j] = a[i][j] - b[i][j];
            }
        }
        return res;
    }

    // 传统矩阵乘法（小规模终止条件）
    private static int[][] traditionalMultiply(int[][] a, int[][] b) {
        int n = a.length;
        int[][] res = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    res[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        return res;
    }

    // Strassen分治递归函数
    private static int[][] strassen(int[][] a, int[][] b) {
        int n = a.length;
        // 终止条件：n=1，直接相乘；n≤2，用传统乘法（避免递归过深）
        if (n <= 2) {
            return traditionalMultiply(a, b);
        }

        // 拆分：分成4个n/2子矩阵
        int mid = n / 2;
        int[][] a11 = new int[mid][mid];
        int[][] a12 = new int[mid][mid];
        int[][] a21 = new int[mid][mid];
        int[][] a22 = new int[mid][mid];
        int[][] b11 = new int[mid][mid];
        int[][] b12 = new int[mid][mid];
        int[][] b21 = new int[mid][mid];
        int[][] b22 = new int[mid][mid];

        // 填充子矩阵
        for (int i = 0; i < mid; i++) {
            for (int j = 0; j < mid; j++) {
                a11[i][j] = a[i][j];
                a12[i][j] = a[i][j + mid];
                a21[i][j] = a[i + mid][j];
                a22[i][j] = a[i + mid][j + mid];

                b11[i][j] = b[i][j];
                b12[i][j] = b[i][j + mid];
                b21[i][j] = b[i + mid][j];
                b22[i][j] = b[i + mid][j + mid];
            }
        }

        // 求解：计算7个中间乘积
        int[][] m1 = strassen(add(a11, a22), add(b11, b22));
        int[][] m2 = strassen(add(a21, a22), b11);
        int[][] m3 = strassen(a11, subtract(b12, b22));
        int[][] m4 = strassen(a22, subtract(b21, b11));
        int[][] m5 = strassen(add(a11, a12), b22);
        int[][] m6 = strassen(subtract(a21, a11), add(b11, b12));
        int[][] m7 = strassen(subtract(a12, a22), add(b21, b22));

        // 合并：组合出结果子矩阵
        int[][] c11 = add(subtract(add(m1, m4), m5), m7);
        int[][] c12 = add(m3, m5);
        int[][] c21 = add(m2, m4);
        int[][] c22 = add(subtract(add(m1, m3), m2), m6);

        // 拼接结果矩阵
        int[][] res = new int[n][n];
        for (int i = 0; i < mid; i++) {
            for (int j = 0; j < mid; j++) {
                res[i][j] = c11[i][j];
                res[i][j + mid] = c12[i][j];
                res[i + mid][j] = c21[i][j];
                res[i + mid][j + mid] = c22[i][j];
            }
        }
        return res;
    }

    // 入口方法
    public static int[][] multiply(int[][] a, int[][] b) {
        return strassen(a, b);
    }

    // 测试
    public static void main(String[] args) {
        int[][] a = {
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12},
                {13, 14, 15, 16}
        };
        int[][] b = {
                {17, 18, 19, 20},
                {21, 22, 23, 24},
                {25, 26, 27, 28},
                {29, 30, 31, 32}
        };
        int[][] res = multiply(a, b);
        System.out.println("乘积矩阵：");
        for (int[] row : res) {
            System.out.println(Arrays.toString(row));
        }
    }
}